package com.mgq.algorithm.twotree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 搜索二叉树
 * 每一棵树的左子树的值都比根小,每一棵右子树的值都比根大
 * 例如
 *     4
 *    / \
 *   2   5
 *  / \
 * 1  3
 */
public class BST {
    /**
     * 版本1
     * 判断一个树是否为搜索二叉树
     * 解决办法: 中序遍历,判断整个结果是否为升序
     * 递归解决.
     *
     * @param node
     * @return
     */
    public boolean isBST(TreeNode node) {
        List<Integer> list = new ArrayList<>();
        if (node == null) return true;
        isBST(node.left);
        //逻辑在这
        list.add(node.val);
        isBST(node.right);
        Integer preVal = Integer.MIN_VALUE;
        for (Integer value : list) {
            if (value <= preVal) {
                return false;
            }
            preVal = value;
        }
        return true;
    }

    /**
     * DP解决
     * 1.找共同点
     * 1.左树和右树都是二叉搜索树
     * 2.左树的最大值<当前值
     * 3.右树的最小值>当前值
     *
     * 出现了问题. 对每个节点的要求不一样,但是因为是递归,又要求对每个节点的要求一样,才是递归
     *
     * 解决办法:
     * 不管什么树,都返回最大值,最小值
     *
     * 可能性
     * 1种可能, 1,2,3都满足
     *
     * 整理条件
     * 1.是否是搜索二叉树
     * 2.最大值
     * 3.最小值
     *
     * @param node
     * @return
     */
    public boolean isBST4(TreeNode node) {
        return process(node).isBST;
    }

    public ReturnData process(TreeNode node) {
        if (node == null) {
            //此处最大值和最小值没办法确定.因此我们返回null
            return null;
        }
        ReturnData leftReturn = process(node.left);
        ReturnData rightReturn = process(node.right);

        //我们需要返回的3个值
        boolean isBST=true;
        int max=node.val;
        int min=node.val;
        //考虑对我自己来说,怎么返回我的树的最小值和最大值
        //当然最小值就是我左树的最小值和我,还有我右边树的最小值的进行比较
        //最大值就是我左树的最大值和我,还有我右边树的最大值的值进行比较
        if (leftReturn != null) {
            min=Math.min(leftReturn.min,node.val);
            max=Math.max(leftReturn.max,node.val);
        }
        if (rightReturn != null) {
            min=Math.min(rightReturn.min,node.val);
            max=Math.max(rightReturn.max,node.val);
        }
        //构造isBST条件 (违规条件) 左树不是搜索树,或者左树的最大值已经大于等于我了
        if (leftReturn != null && (!leftReturn.isBST || leftReturn.max >= node.val)) {
            isBST= false;
        }
        if (rightReturn != null && (!rightReturn.isBST || rightReturn.min <= node.val)) {
            isBST= false;
        }
        return new ReturnData(isBST, max, min);
    }
    /**
     * 递归优化
     * 记录前一次值.每次比较
     * @param node
     * @return
     */
    Integer preVal = Integer.MIN_VALUE;

    public boolean isBST3(TreeNode node) {
        if (node == null) return true;
        //检查左子树是否为搜索树
        boolean isBST = isBST(node.left);
        //左边不是BST
        if (!isBST) {
            return false;
        }
        //不是升序
        if (node.val <= preVal) {
            return false;
        } else {
            //赋值给preVal
            preVal = node.val;
        }
        return isBST(node.right);
    }

    /**
     * 基于栈来解决
     *
     * @param node
     * @return
     */
    public boolean isBST2(TreeNode node) {
        Integer preVal = Integer.MIN_VALUE;
        if (node == null) return true;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || node != null) {
            //把左边全部压栈
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            //压入完成后,弹出
            node = stack.pop();
            //这打印
            // System.out.println(node);
            if (node.val <= preVal) {
                return false;
            } else {
                preVal= node.val;
            }
            //右边继续
            node = node.right;
        }
        return true;
    }
}
class ReturnData{
    boolean isBST;
    int max;
    int min;

    public ReturnData(boolean isBST, int max, int min) {
        this.isBST = isBST;
        this.max = max;
        this.min = min;
    }
}